Digital halftoning is a technique employing digital image processing to produce a halftone output image from a continuous-tone input image. In the digital halftoning technique, a continuous-tone image is sampled, for example, with a scanner and the samples are digitized and stored in a computer. The digitized samples (or "pixels") consist of discrete values typically ranging from 0 to 255. To reproduce this image on an output device capable of printing dots of one gray level (e.g. black) it is necessary to create the sensation of multiple gray levels by suitably distributing the printed dots in the output image. This is accomplished by converting the continuous-tone image to a binary output image using some form of halftoning technique.
One prior art method of digital halftoning is known as error diffusion. FIG. 1 shows a block diagram describing a basic error diffusion technique. The continuous-tone input value for column i, and row j of the input image is given by y.sub.i,j. For purposes of illustration it will be assumed that the continuous-tone input values span the range from 0 to 255. The continuous-tone input value for the current input pixel is thresholded 10 to form the output value b.sub.i,j. The threshold operator will return a 0 for any continuous-tone input value below the threshold, and a 255 for any continuous-tone input value above the threshold. A difference signal generator 12 receives the continuous-tone input value and the output value, and produces a difference signal representing the error introduced by the thresholding process. The difference signal is multiplied by a series of error weights using a weighted error generator 14, and is provided to an adder 16 which adds the weighted difference signal to the continuous-tone input values of nearby pixels which have yet to be processed to form modified continuous-tone input values. The propagation of the errors made during the quantization process to the nearby pixels insures that the arithmetic mean of the pixel values is preserved over a local image region.
FIG. 2 illustrates a typical set of error weights 14 which can be used to distribute the errors to the nearby pixels.
FIG. 3 shows a typical image generated using this simple error diffusion technique.
An artifact that is typically associated with error diffusion halftoning techniques is known as "worms." Worms are formed when the black or white output pixels appear to string together in an area which should be otherwise uniform. Worm artifacts can be clearly seen in several areas of the sample image shown in FIG. 3, such as the light and dark ends of the gray wedge. Several of these worm artifacts are labeled as 18A-C. Many modifications to the basic error diffusion technique have been described which attempt to eliminate these worm artifacts. One such modification has been described by Goertzel et al. in U.S. Pat. No. 4,654,721 issued Mar. 31, 1987. In their disclosure, each input pixel is represented by a block of output pixels. The appearance of worms is avoided by employing a random number generator to determine the distribution of error between two adjacent blocks of pixels, such that a random fraction of error is distributed to one block and the remainder of the error is distributed to the other. In another technique, sometimes called error diffusion with dither, the error criterion is randomly varied to reduce the appearance of worms. Although these techniques, and others like them, reduce the appearance of worms, they also increase the random noise in the output image. To the extent that this random noise occurs in the frequencies visible to the human viewer, the image is thereby degraded.
A more desirable approach has been disclosed by Sullivan (U.S. Pat. No. 5,051,844 issued Sep. 24, 1991). This method will be referred to as visual error diffusion. Sullivan teaches the use of a visual filter derived from the response of the human visual system to compute a visually perceived output value. The output level is chosen which gives the smallest error between the continuous-tone input value and the visually perceived output value. The error signal which is propagated to the nearby image pixels is then computed by taking the difference between the continuous-tone input value and the visually perceived output value rather than the output value itself. FIG. 4 illustrates a flow diagram for this method. The simple threshold 10 in the conventional error diffusion method has been replaced by a selector 30 which determines the output pixel value b.sub.i,j. The selection by the selector 30 is made by using a causal visual filter 31 to filter the previously computed output pixel values together with each of the possible output levels for the current pixel 32 to compute the visually perceived output value for each possible output level. For a binary output device there will be two possible output levels corresponding to a black or a white pixel, but this method can be extended to multi-level output devices by considering more than two possible output levels. The output pixel value is chosen which gives the smallest difference between the continuous-tone input value and the visually perceived output level. The resulting error is then calculated for the current pixel by a difference signal generator 33 which computes a difference signal between the continuous-tone input value and the visually perceived output value 34. As with the conventional error diffusion technique, this difference signal is then weighted by a series of error weights W.sub.i,j using a weighted error generator 35, and is added 36 to the continuous-tone input values of nearby pixels which have yet to be processed to form modified continuous-tone input values. The causal visual filter function is computed from the frequency response of the human visual system as described by Sullivan. An example of a 4.times.7 causal visual filter function is shown in FIG. 5. The array element 40 is used to weight the possible output levels for the present pixel, and the remaining array elements are used to weight the nearby output values which have been previously computed. (This causal visual filter function is a normalized version of the one disclosed by Sullivan.) A similar 8.times.15 causal visual filter function is shown in FIG. 6. The size of the causal visual filter function array is related to the parameters such as viewing distance and sample spacing on the document in the equations given by Sullivan. In this case, the array element 42 is used to weight the possible output levels for the present pixel, and the remaining array elements are used to weight the nearby output values which have been previously computed. FIG. 7 shows a sample image generated using this technique with the 8.times.15 causal visual filter function. The worm artifacts 18A-C which were shown in FIG. 3 have been eliminated.
Although visual error diffusion has the result of reducing the appearance of worms to a large degree without the introduction of undesirable noise, a side effect of this method is that artifacts are generated near edges, lines, and isolated pixels in the image. One type of artifact can be referred to as "ghost pixels." Examples of ghost pixels artifacts 20A-C can be observed around the isolated pixels and the edges in the image shown in FIG. 7. The origin of these ghost pixel artifacts can be traced to the fact that the selection process is comparing the visually perceived output image to the unfiltered input image. So, for example, consider the case where the input image contains an isolated black pixel on a white background. The visual error diffusion technique will place white pixels in most of the area corresponding to the white background, but when it comes time to make a selection for the black pixel it will visually filter the output pixels in the surrounding area. Since most of these pixels will be white, the visually perceived output level for a white output pixel will be white, but the visually perceived output level for a black output pixel will be light gray rather than black. Since the light gray visually perceived output level will be closer to the desired black input level than the white visually perceived output level, the correct black output level will be chosen. However, the resulting error signal corresponding to the difference between the black input level and the light gray visually perceived output level will be quite large. This error will then be propagated to the surrounding continuous-tone input pixels. As a result, when the nearby white background pixels are processed, one or more of these pixels may be rendered as black output pixels.
The artifacts can be even more severe on edges between uniform patches of different gray levels where anisotropic overshoots are formed. Although this artifact has a sharpening effect on the image, it is not necessarily desirable because the degree of sharpening can not be controlled independent of the worm reduction, and additionally the effect is anisotropic so that the apparent sharpening is not symmetric. Examples of the anisotropic sharpening of edges 19A and B can be seen in FIG. 7. As with the ghost pixel artifacts, the origin of the anisotropic sharpening artifacts can be traced to the fact that the selection process is comparing the visually perceived output image to the unfiltered input image.